"""
插入排序 递归实现 升序排序

补充：
一、递归的本质：“自己调用自己” 的核心逻辑：
递归的核心思想是：把一个大问题拆解成和它相似但规模更小的子问题，直到子问题小到可以直接解决（终止条件），再通过子问题的解反推大问题的解。
比如本题的插入排序递归：
大问题：排序长度为 n 的数组 arr。
子问题：先排序长度为 n-1 的子数组（前 n-1 个元素），然后把第 n 个元素插入到正确位置。
终止条件：当数组长度 n <= 1 时，数组天然有序，无需排序（直接返回）。

二、编写递归代码的 3 个关键步骤
以本题的插入排序为例，一步步对应：
1. 明确 “终止条件”（基线条件）
递归不能无限调用，必须有一个 “停止点”—— 当问题小到一定程度时，直接返回结果。
2. 拆解问题：“当前层” 和 “子问题” 的关系
把当前问题拆解为 “子问题的解 + 当前层的操作”。
在本例中：
子问题：先解决 “排序前 n-1 个元素”（通过递归调用 insertion_sort_recursive(arr, n-1) 实现）。
当前层操作：子问题解决后（前 n-1 个元素已有序），只需把第 n 个元素（arr[n-1]）插入到前 n-1 个元素中的正确位置。
3. 确保 “子问题规模在缩小”
每次递归调用时，传递的参数必须让问题规模比当前小（否则会无限递归）。


三、理解递归的 “执行流程”：从 “递” 到 “归”
递归的执行分为两个阶段：
“递” 的阶段：从大问题出发，不断调用自身，拆解为更小的子问题，直到触发终止条件。比如对 n=5 的数组，递归调用顺序是：n=5 → n=4 → n=3 → n=2 → n=1（触发终止条件，开始返回）。
“归” 的阶段：从终止条件开始，逐步返回，同时执行 “当前层操作”，合并子问题的解。比如：n=1 返回后，处理 n=2（插入第 2 个元素）→ 返回后处理 n=3（插入第 3 个元素）→ ... 直到 n=5 处理完，排序完成。

总结
递归的核心不是 “循环调用”，而是 “拆解问题 + 终止条件”。


时间复杂度分析
时间复杂度计算
递归调用次数：共 n-1 次（从 n 递归到 1）。
每次递归的插入操作：插入第 k 个元素（k 从 2 到 n）时，最多需要与前 k-1 个元素比较并移动（最坏情况，数组完全逆序）。
总操作次数为：1 + 2 + 3 + ... + (n-1) = n(n-1)/2
时间复杂度：
最坏情况（逆序数组）：O(n^2)
最好情况（已排序数组）：O(n)（插入时无需移动元素，仅递归 n-1 次）
平均情况：O(n^2)

总结
递归版插入排序通过 “先递归排序前 n-1 个元素，再插入第 n 个元素” 实现，逻辑与迭代版一致，但借助递归简化了循环结构。
时间复杂度与迭代版相同(最坏和平均为 O(n^2))，
但递归调用会带来额外的栈空间开销(空间复杂度 O(n)，迭代版为O(1))。因此，实际应用中迭代版更常用，但递归版有助于理解 “分治” 和 “缩小问题规模” 的思想。

"""


def insertion_sort_recursive(arr, n):
    """
    递归版插入排序
    :param arr: 待排序数组
    :param n: 当前需要处理的数组长度
    """
    # 基线条件：若数组长度 <= 1，无需排序
    if n <= 1:
        return
    """
    在递归版插入排序中，数组arr是通过引用传递的，因此下一层递归对数组的修改会直接反映到上一层，不需要显式返回数组对象。
    具体来说：
    Python 中列表（list）是可变对象，当函数接收列表作为参数时，传递的是列表的引用（内存地址），而非副本。
    递归调用insertion_sort_recursive(arr, n - 1)时，函数操作的是同一个arr对象。
    当递归处理完前n-1个元素后，该层递归对arr的排序修改会直接作用于原始数组，上一层递归可以直接使用已经排好序的前n-1个元素。
    """
    insertion_sort_recursive(arr, n - 1)
    key = arr[n - 1]  # 待插入的元素
    i = n - 2  # 从已排序部分的最后一个元素开始比较
    # 移动比 key 大的元素，为 key 腾出位置
    while i >= 0 and arr[i] > key:
        arr[i + 1] = arr[i]  # 元素后移
        i -= 1
    # 将 key 插入到正确位置
    arr[i + 1] = key

# 测试示例
arr = [12, 11, 13, 5, 6]
n = len(arr)
insertion_sort_recursive(arr, n)
print("排序后数组：", arr)  # 输出：[5, 6, 11, 12, 13]